import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeMap;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-30
 * Time: 16:11
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution2 {
    public int[] postorderTraversal (TreeNode root) {
        //迭代，还是使用栈的方法
        Stack<TreeNode> stack=new Stack<>();
        ArrayList<Integer> list=new ArrayList<>();
        //标记遍历过的点
        TreeNode pre=null;
        while ( root!=null|| !stack.isEmpty() ) {
            while ( root!=null ){
                stack.push(root);
                root = root.left;
            }
            //弹出的就是最左边的节点
            TreeNode cur=stack.pop();
            if(cur.right==null || cur.right==pre){
                //没有右节点了就把根节点加入顺序表
                list.add( cur.val );
                //标记这个节点为访问过
                pre=cur;
            }else{
                //有右孩子就把这个节点加入栈，因为有右节点的话需要先遍历右节点
                //注意不是直接把右节点加入栈，因为根节点已经出栈，直接把右节点入栈的话，就访问不到了
                stack.push(cur);
                root = cur.right;
            }
        }
        int[] ret=new int[list.size()];
        for(int i = 0; i <list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }
}
